class MinHeap:
    def __init__(self, array=None):
        self.heap = []
        if array is not None:
            self.heap = array
            self._heapify()
    
    def push(self, value):
        """将新元素插入堆中并维护堆性质"""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)
    
    def pop(self):
        """移除并返回堆顶元素（最小值）"""
        if not self.heap:
            return None
        self._swap(0, len(self.heap) - 1)
        min_val = self.heap.pop()
        self._sift_down(0)
        return min_val
    
    def peek(self):
        """获取但不移除堆顶元素"""
        return self.heap[0] if self.heap else None
    
    def __len__(self):
        return len(self.heap)
    
    def _heapify(self):
        """将列表转换为堆，时间复杂度O(n)"""
        n = len(self.heap)
        start = (n - 2) // 2  # 最后一个非叶子节点
        for i in range(start, -1, -1):
            self._sift_down(i)
    
    def _sift_up(self, index):
        """从下向上调整堆"""
        while index > 0:
            parent = (index - 1) // 2
            if self.heap[index] >= self.heap[parent]:
                break
            self._swap(index, parent)
            index = parent
    
    def _sift_down(self, index):
        """从上向下调整堆，用于弹出堆顶元素后的堆调整
        Args:
            index: 当前需要调整的节点索引
        """
        n = len(self.heap)  # 获取堆的大小
        while True:  # 不断循环直到堆性质被满足
            min_idx = index  # 初始化最小值索引为当前节点索引
            left = 2 * index + 1  # 计算左子节点索引
            right = 2 * index + 2  # 计算右子节点索引
            
            # 遍历左右子节点，找出最小值索引
            for child in [left, right]:
                # 如果子节点索引有效且值小于当前最小值节点
                if child < n and self.heap[child] < self.heap[min_idx]:
                    min_idx = child  # 更新最小值索引
            
            # 如果当前节点已经是最小值（符合小根堆性质）
            if min_idx == index:
                break  # 终止循环，调整完成
                
            # 交换当前节点和最小值节点的值
            self._swap(index, min_idx)
            # 更新当前索引指向交换后的位置，继续向下调整
            index = min_idx  
    
    def _swap(self, i, j):
        """交换堆中两个元素"""
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]


# 初始化堆
heap = MinHeap()
heap.push(3)
heap.push(1)
heap.push(4)
heap.push(1)
heap.push(5)

print(heap.pop())  # 输出: 1
print(heap.pop())  # 输出: 1
print(heap.pop())  # 输出: 3

# 通过列表初始化
heap2 = MinHeap([3, 1, 4, 1, 5])
print(heap2.pop())  # 输出: 1



# []